﻿public class Trie
{
    //属性
    private bool isEnd;
    Trie[] children;//26个孩子

    public Trie()
    {
        children=new Trie[26];
        isEnd=false;
    }

    public void Insert(string word)
    {

        Trie curNode = this;
        for (int i = 0; i < word.Length; i++) { //分别存放字符
            char ch = word[i];
            int index = ch - 'a';//在字母表的第几个
            if (curNode.children[index] == null) {

                curNode.children[index]=new Trie();
            }

            curNode=curNode.children[index];
        }
        curNode.isEnd=true;


    }

    public bool Search(string word)
    {
        Trie node= SearchPrefix(word);

         //这个字母必须还是一个单词的结尾
        
            return node != null && node.isEnd;
        


    }

    public bool StartsWith(string prefix)
    {
       return SearchPrefix(prefix) !=null;//只有有这个前缀就行
    }
    private Trie SearchPrefix(string prefix)
    {

        Trie curNode = this;
        for (int i = 0; i < prefix.Length; i++)
        { //分别存放字符
            char ch = prefix[i];
            int index = ch - 'a';//在字母表的第几个
            if (curNode.children[index] == null)
            {

                return null;//没有找到这个前缀
            }

            curNode = curNode.children[index];//继续寻找
        }
        return curNode;//中间没有返回，说明每一个前缀的字母都找到了，返回最后一个字母 的NOde


    }

}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.Insert(word);
 * bool param_2 = obj.Search(word);
 * bool param_3 = obj.StartsWith(prefix);
 */

class Program208 {


    static void Main208(string[] args)
    {
        Trie trie = new Trie();
        
        trie.Insert("apple");
        Console.WriteLine(trie.Search("apple"));  // 返回 True
        Console.WriteLine(trie.Search("app"));  // 返回 False
        Console.WriteLine(trie.StartsWith("app")) ; // 返回 True
        trie.Insert("app");
        Console.WriteLine(trie.Search("app"));   // 返回 True


    }
}